Research Seminar in Combinatorics and Graph Theory (238902)

Winter semester 2011/12
last updated: 22.10.2011
Announced as 238901 (because the course 238902 is still awaiting senate approval).

Structural Graph Theory and Algorithmic Meta-theorems


NEW (tba): List of topics for seminar talks.

NEW (tba): Slides of given lectures


For those graduate students who have already taken 238901 before,
but on another topic, arrangements will be found to get credit again.

Lecturer: Prof. J.A. Makowsky and participants
NEW TIME: Sunday, 12:30-14:30
New Place: Taub 4


Prerequisites: Some elementary graph theory, Computability.
Format: Two hours frontal presentations.
Requirements: Edited version of frontal presentation or final project.

Outline

One of the great achievements in graph theory is the emergence of a structural theory initiated by the work of N. Robertson and P. Seymour and their students and collaborators. The prototype of a structural theorem concerns the characterization of minor closed graph classes and the notion of tree-width of a graph. More recently, other notions of width emerged, such as clique-width and rank-width, for which there are also structural theorems.

The basic theory is well covered in the book Graph Theory by R. Diestel.

The structural theory of graphs also led to algorithmic meta-theorems, theorems of the form

Every problem of the from xxxxx has certain algorithmic properties

Here xxxxx can be a definability condition like contsraint satisfaction problems, classes of graphs of fixed width definable in some formalism, etc. A survey of such theorems can befound in my recently edited book, available on line, in particular the paper by http://www.cs.technion.ac.il/~janos/COURSES/238902-11/ The first meeting of the seminar is on

Sunday, 30 October, 12:30, Taub 4

Feel free to contact me before that if you have any questions.